package leetcodev1.链表;

public class Solution {

    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int leftSum = 0, rightSum = sum;
        for (int i = 0; i < nums.length; i++) {
            rightSum -= nums[i];//减去中心位
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];//将中心位加入左边
        }
        return -1;
    }

    public String longestCommonPrefix(String[] strs) {
        String ret = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (ret.length() == 0) {
                return "";
            }

            String tmp = strs[i];
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < ret.length() && j < tmp.length(); j++) {
                if (ret.charAt(j) != tmp.charAt(j)) {
                    break;
                }
                sb.append(ret.charAt(j));
            }
            ret = sb.toString();
        }
        return ret;
    }

    //最长回文串
    //回文串的起点 s[i]==s[i+1]
    //动态规划
    public String longestPalindrome(String s) {
        //row代表起点 column代表终点
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }

        int resIdx = 0, resLen = 1;
        for (int j = 1; j < length; j++) {//终点
            for (int i = 0; i < j; i++) {//起点
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                    continue;
                }
                if (j - i < 3) {
                    dp[i][j] = true;//奇数个是回文
                } else {
                    dp[i][j] = dp[i + 1][j - 1];//继承子串的结果
                }


                if (dp[i][j] && j - i + 1 > resLen) {
                    resIdx = i;
                    resLen = j - i + 1;
                }
            }
        }
        return s.substring(resIdx, resIdx + resLen);
    }

}
